package com.asia.driver.dynamic;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;

public class DesignIdea {
    public boolean checkSubarraySum(int[] nums, int k) {
        int[] preSums = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            preSums[i + 1] = preSums[i] + nums[i];
        }

        HashMap<Integer, Integer> complementMapIdx = new HashMap<>();

        for (int i = 0; i < preSums.length; i++) {
            int complement = preSums[i] % k;
            if (complementMapIdx.containsKey(complement)) {
                if (i - complementMapIdx.get(complement) > 1) {
                    return true;
                }
            } else {
                complementMapIdx.put(complement, i);
            }
        }

        return false;
    }

    public int findMaxLength(int[] nums) {

        int[] preSum = new int[nums.length + 1];
        for (int i = 1; i < preSum.length; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }

        int n = 0;
        for (int i = 1; i < preSum.length; i++) {
            if (preSum.length - i <= n) break;
            for (int j = preSum.length - 1; j >= 1; j--) {
                int sum = preSum[j] - preSum[i - 1];
                // 区间长度为偶数并且这段区间值的和为长度的一半
                int lenth = j - i + 1;
                if (lenth < n) break;
                if ((lenth & 1) == 0 && lenth == sum * 2) {
                    n = Math.max(n, lenth);
                    break;
                }
            }
        }
        return n;
    }


    // 归并算法、快速排序
    public int[] sortArray(int[] nums) {
//            temp = new int[nums.length];
//            mergeSort(nums, 0, nums.length - 1);
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    private int[] temp;

    // 归并排序
    private void mergeSort(int[] nums, int start, int end) {
        if (start == end) {
            return;
        }

        int mid = (start + end) / 2;
        mergeSort(nums, start, mid);
        mergeSort(nums, mid + 1, end);

        merge(nums, start, mid, end);

    }

    private void merge(int[] nums, int start, int mid, int end) {
        for (int i = start; i <= end; i++) {
            temp[i] = nums[i];
        }
        int left = start;
        int right = mid + 1;
        for (int i = start; i <= end; i++) {

            if (left > mid) {
                nums[i] = temp[right++];
            } else if (right > end) {
                nums[i] = temp[left++];
            } else {
                if (temp[left] < temp[right]) {
                    nums[i] = temp[left++];
                } else {
                    nums[i] = temp[right++];
                }
            }

        }
    }


    // 快速排序
    private void quickSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int idx = partition(nums, start, end);
        quickSort(nums, start, idx - 1);
        quickSort(nums, idx + 1, end);
    }

    private int partition(int[] nums, int start, int end) {
        int base = nums[start];
        int i = start;
        int j = end;
        while (i < j) {
            while (i < j && nums[j] >= base) {
                // 后指针找比base小的数
                j--;
            }
            while (i < j && nums[i] <= base) {
                // 前指针找比base大的数
                i++;
            }

            // 大的往后放，小的往前放
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;

        }

        nums[start] = nums[i];
        nums[i] = base;

        return i;
    }


    public boolean carPooling(int[][] trips, int capacity) {
        int[] diff = new int[1000];
        for (int i = 0; i < trips.length; i++) {
            int numPassengers = trips[i][0];
            int from = trips[i][1] - 1;
            int to = trips[i][2] - 1;
            diff[from] += numPassengers;
            diff[to] -= numPassengers;
        }

        int[] res = new int[1000];
        res[0] = diff[0];
        if (res[0] > capacity) return false;
        for (int i = 1; i < diff.length; i++) {
            res[i] = diff[i] + res[i - 1];
            if (res[i] > capacity) {
                return false;
            }
        }
        return true;

    }

    public String reverseWords(String s) {
        s = s.trim();
        char[] chars = s.toCharArray();
        int left = 0;
        int maxIdx = chars.length - 1;
        // 反转整个字符串
        reverse(chars, left, maxIdx);

        StringBuilder sb = new StringBuilder();
        // 反转每个单词
        int idx = 0;
        while (idx <= maxIdx) {
            int start = -1;
            int end = -1;
            while (start == -1 || end == -1 && idx <= maxIdx) {
                if (chars[idx] != ' ' && start == -1) {
                    start = idx;
                }
                if (start != -1 && chars[idx] == ' ' && end == -1) {
                    end = idx - 1;
                }
                idx++;
            }
            if (idx > maxIdx && end == -1) {
                end = maxIdx;
            }
            reverse(chars, start, end);
            for (int i = start; i <= end; i++) {
                sb.append(chars[i]);
            }
            sb.append(" ");
        }
        return sb.toString().trim();
    }

    private void reverse(char[] chars, int left, int right) {

        while (left < right) {
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            left++;
            right--;
        }
    }

    public int compareVersion(String version1, String version2) {
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");

        int idx = 0;
        while (idx < v1.length || idx < v2.length) {
            int v1Num=-1;
            int v2Num=-1;
            if (idx >= v1.length) {
                v1Num=0;
                v2Num=Integer.parseInt(v2[idx]);
            }else if (idx >= v2.length) {
                v2Num=0;
                v1Num=Integer.parseInt(v1[idx]);
            }else {
                v1Num=Integer.parseInt(v1[idx]);
                v2Num=Integer.parseInt(v2[idx]);
            }
            if (v1Num>v2Num){
                return 1;
            }else if (v1Num<v2Num){
                return -1;
            }else {
                idx++;
                continue;
            }
        }
        return 0;
    }

    public int[] twoSum(int[] numbers, int target) {
        int l = 0;
        int r = numbers.length - 1;
        while (numbers[l] + numbers[r] != target) {
            if (numbers[l] + numbers[r]<target){
                l++;
            }else {
                r--;
            };
        }
        int[] res={l+1,r+1};
        return res;
    }

    public int findKthLargest(int[] nums, int k) {
        if (nums.length==1)  return 1;
        quickSort(nums,0,nums.length-1,nums.length-k);
        return nums[nums.length-k];
    }

    private void quickSort(int[] nums, int start, int end, int k) {
        if (start >= end) {
            return;
        };

        int base = nums[start];
        int l = start;
        int r = end;
        while (l < r) {
            while (l < r && nums[r] >= base) {
                r--;
            }
            while (l < r && nums[l] <= base) {
                l++;
            }

            if (l != r) {
                int temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;
            }
        }

        nums[start] = nums[l];
        nums[l] = base;
//            if (l == k) {
//                return;
//            }

        quickSort(nums, start, l - 1, k);
        quickSort(nums, l + 1, end, k);
    }

    public void sortColors(int[] nums) {
        for (int i = nums.length-1; i >=0; i--) {
            for (int j = i-1; j >=0; j--) {
                if (nums[i]<nums[j]){
                    int temp=nums[j];
                    nums[j]=nums[i];
                    nums[i]=temp;
                }
            }
        }
    }

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] temp = Arrays.copyOf(nums1, nums1.length);
        int idx = 0;
        int idx1 = 0;
        int idx2 = 0;
        while (idx1 < m && idx2 < n) {
            if (temp[idx1] > nums2[idx2]) {
                nums1[idx] = nums2[idx2];
                idx2++;
            } else {
                nums1[idx] = temp[idx1];
                idx1++;
            }
            idx++;
        }
        if (idx1 >= m) {
            for (int i = idx2; i < n; i++) {
                nums1[idx] = nums2[i];
                idx++;
            }
        } else {
            for (int i = idx1; i < m ; i++) {
                nums1[idx] = temp[i];
                idx++;
            }
        }
    }


    // 快速排序
    private void quickSort2(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int idx = partition(nums, start, end);
        quickSort(nums, start, idx - 1);
        quickSort(nums, idx + 1, end);
    }

    private int partition2(int[] nums, int start, int end) {
        int base = nums[start];
        int i = start;
        int j = end;
        while (i < j) {
            while (i < j && nums[j] >= base) {
                // 后指针找比base小的数
                j--;
            }
            while (i < j && nums[i] <= base) {
                // 前指针找比base大的数
                i++;
            }

            // 大的往后放，小的往前放
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;

        }

        nums[start] = nums[i];
        nums[i] = base;

        return i;
    }


}
